Isomorphic Strings || Word Pattern

发表于

Isomorphic Strings

Question

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,

Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Analysis

  • 利用两个num（大小256代表所有可能字符的个数），用来记录某种字符上次出现的位置
  • num需赋值小于0以避免下标大于等于0的情况

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] str1=s.toCharArray();
        char[] str2=t.toCharArray();
        int[] num1=new int[256];
        int[] num2=new int[256];
        Arrays.fill(num1,-1);
        Arrays.fill(num2,-1);
        
        for(int i=0;i<str1.length;i++){
            if(num1[str1[i]]!=num2[str2[i]])
                return false;
            num1[str1[i]]=i;
            num2[str2[i]]=i;
        }
        return true;
    }
}

Word Pattern

Question

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Analysis

  1. 蠢蠢的方法
    • Map保存char到string的映射，Set用以判断是否有多个char映射到同一个String
    • 第一遍遍历保存映射，第二次遍历查看是否有不符合映射标准的，假如有返回false
  2. LeetCode Discuss
    • 思路跟上题一样，保存每个映射对应的上次出现的位置，可以用一个不限定类型的map取代两个map
    • map.put的返回值是之前与 key 关联的值，如果没有针对 key 的映射关系，则返回 null

Code

  1. Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] word=str.split(" ");
        HashMap<Character,String> map=new HashMap();
        HashSet<String> set=new HashSet();
        if(pattern.length()!=word.length)  return false;
        
        for(int i=0;i<word.length;i++){
            char c=pattern.charAt(i);
            if(!map.containsKey(c)){
                if(!set.contains(word[i])){
                    map.put(c,word[i]);
                    set.add(word[i]);
                }else 
                    return false;
            }
        }
        
        for(int i=0;i<word.length;i++){
            char c=pattern.charAt(i);
            if(!map.get(c).equals(word[i]))
                return false;
        }
        
        return true;
    }
}
  1. Version 2 (Short one)
1
2
3
4
5
6
7
8
9
10
public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (Integer i=0; i<words.length; ++i)
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
            return false;
    return true;
}